Modern trunked radio communications systems typically include geographically distributed "satellite" receiving sites in addition to one or more main transmitting site. Consider a simple system including only one main transmitting/repeater site. The main transmitting/repeater site is typically located at a relatively high elevation (e.g., on the top of a hill, mountain or tall building) and generally is provided with relatively high powered RF transmitters to permit the site to "cover" a large desired geographical service area. The main site transmitter output power and other factors contributing to the "effective radiated power" (ERP) are selected so that signals transmitted by the main site can be received at acceptable signal strength throughout the desired service area.
Unfortunately, most or all of the mobile and portable RF transceivers served by the main site cannot provide the same high effective radiated power as is provided by the main site because of several limiting factors.
While the main site transmitter power output can be in the range of several hundreds or thousands of watts RF, a mobile transceiver may be capable of providing only 5 to 25 watts of RF at its output and portable (e.g., hand held) transceivers may be capable of generating even less power (e.g., on the order of 1 watt or even less). Size and cost limitations to a large degree dictate the limited RF power outputs of mobile and portable units, but power source limitations are perhaps the most critical factor. A portable transceiver using a few small nickel-cadmium battery cells as its power source can provide only low power output levels. Mobile transceivers can obtain additional power from a vehicle electrical system, but even this power source imposes serious constraints on the maximum power supply current the transceiver can draw.
Since the various mobile and portable transceivers within a radio communications system have vastly lower effective radiated power outputs than do the transmitters at the main site, all mobile/portable transceivers within the service area can typically receive the strong transmissions from the main site but the receivers located at the main site may not receive the weaker transmissions from the mobile and portable transceivers (or may receive the transmissions at signal strengths which are too low to provide useful, reliable communications). In other words, the "talk in" range of the main site is typically less than its "talk out" range.
Multiple receiving sites have been employed in the past to help solve this problem. Typically, so-called "satellite" receiving sites are provided at various geographical locations within the service area. The main site is provided with a full complement of receivers, and similar receivers are provided at each satellite receiving site. When a mobile or portable receiver transmits within the service area, some or all of the satellite receiving sites and the main site may receive the transmission. Depending upon where in the service area the transmitting mobile/portable happens to be at the time it transmits, some sites will receive the transmission at high signal strength levels, other sites will receive the transmission at lower levels, and some sites may not receive the transmission at all, for example, if an obstruction or very long signal path exists between the mobile/portable and the site.
Of course, the communication system needs to receive a given mobile/portable transmission only once at a useful signal level. It is desirable therefore to select only one version of the received message and to discard or ignore redundant versions of the received message (this process can be called "redundancy removal"). Since the various receiving sites receive a given mobile/portable transmission at different average signal strengths, it may, for example, be desirable in some systems to select the version of the transmission received with the best quality (e.g., highest average signal strength or lowest bit error rate) since that version is most likely to have carried the communicated information reliably and correctly (noise, fading and other effects can degrade reception of weak signals). In many prior art systems, all sites which receive the transmission generate an indication of the quality of the received signal (e.g., based on received signal strength and/or other factors). The overall communication system then typically may "vote" based on the quality indications reported by the different receiving sites to select a single version of the received signal for use. Commonly assigned U.S. Pat. No. 4,317,218 to Perry (1982) describes in detail one example of this type of prior art voting circuit within a repeater station control system. See also, for example, U.S. Pat. No. 4,013,962 to Beseke et al (1977).
Things happen very rapidly in state-of-the-art digital trunking systems such as The General Electric Company 16-PLUS Public Service Trunking (PST) digitally trunked radio communications system. The architecture and operation of this system is disclosed in much greater detail in the following co-pending commonly assigned U.S. patent applications (which are incorporated by reference herein):
U.S. Ser. No. 07/056 922 Childress et al field Jun. 3, 1987, issued Jul. 27, 1990, now U.S. Pat. No. 4,905,302;
U.S. Ser. No. 07/057,046 Childress et al filed Jun. 3, 1987, and
U.S. Ser. No. 07/085,572 Nazarenko et al filed Aug. 14, 1987, issued May 30, 1989, now U.S. Pat. No. 4,835,731.
Briefly, GE's PST system communicates digital data at 9600 baud in "slotted" message frames each having a duration of 30 ms. These "slots" are closely (although not exactly) synchronized in time across all channels (for both inbound and outbound communications) and follow the "slot" timing of the digital control channel. Some messages use only a single slot, while other messages occupy two slots. A mobile transceiver requiring a channel assignment will in GE's preferred system transmit a channel assignment request message in one or more successive predefined time slots on the inbound control channel and then wait for a responsive two-slot channel assignment message to be transmitted by the main site on the outbound control channel. The mobile transceiver expects to receive a response (of some sort) to its request message within a relatively short time period (e.g., so the mobile can rapidly determine if its request was ignored and retransmit the request). In configurations including multiple satellite receiving sites, it is necessary during this short time period for the system to select a single version of the received message and pass it to the main site for processing and response. In a system having a main site and two satellite receiving sites, for example, the following may occur:
(a) the main site receives and decodes the message;
(b) satellite receiving site (1) receives and decodes the message;
(c) satellite receiving site (2) receives and decodes the message;
(d) the main site receives and decodes the message;
(e) satellite receiving sites (1) and (2) and the main site communicate the message versions they received (assuming they each received the message) to a centralized voter (e.g., located at the dispatch console);
(f) the voter "votes" on the versions of the messages received by the main and satellite sites to select a single version of the message (and preferably also discards all non-selected versions while somehow ensuring that the messages being discarded are in fact redundant versions of the same message rather than different messages);
(g) the system processes the selected version of the message and generates an appropriate responsive message; and
(h) the generated responsive message is transmitted over the main site outbound control channel for reception by the mobile.
The term "system latency" refers to the amount of time it takes for a message to propagate through the system. For example, one measure of system latency is the delay from when a mobile transceiver user keys his microphone (e.g., thereby generating a working channel assignment request) to the time the mobile transceiver receives a responsive message back from the system. Obviously, it is desirable to minimize system latency since rapid access and rapid system response provide great advantages in terms of user friendliness, system throughput, and the like. In the GE PST system, this particular system latency parameter has a maximum of 90-100 milliseconds--and the mobile will automatically retransmit its request if such a time period elapses and no response has yet been received. Thus, it is generally necessary for steps (a)-(h) described above to be performed within 100 ms or less in the GE PST system.
For such minimal system latency to be achieved, each of steps (a)-(h) must be performed as rapidly as possible. The delays introduced by some of the steps cannot be significantly reduced because of practical considerations and the laws of physics (e.g., it takes a certain finite amount of time to receive and decode an RF message being transmitted, it takes a finite amount of time to transmit a received message over a landline from a satellite site to a central location, and it takes a certain finite amount of time to transmit a responsive RF message over the control channel). The time required by step (f) to "vote" on one received message and to discard redundant versions of the same message should therefore be minimized in order to reduce overall system latency.
Prior digital voter architectures for multiple receiver site systems have not provided the rapid message handling/selection capabilities required to minimize system latency in high speed digital communications systems.
FIG. 1 is a schematic block diagram of a prior art digital voter architecture 50 used in the past by GE in its Voice Guard Digital Voter (described in greater detail in GE Publication LBI-31600. Voter 50 includes a digital selector 52 and plural digital receivers 54 connected together via a bus 56. In the embodiment shown, digital receiver 54(1) receives messages in digital form from receiver site 1, digital receiver 54(2) receives messages in digital form from receiver site 2, . . . , and digital receiver 54(N) receives messages in digital form from receiver site N. Each receiver 54 stores the messages it receives in a temporary buffer for selection by digital selector 52.
Digital selector 52 must determine which of digital receivers 54 have stored received messages and select one of multiple redundant messages if more than one digital receiver has stored the same received message. In the past, these steps were performed by a polling process over the bus 56. Specifically, digital selector 52 (or some other "bus controller" component) would periodically and successively send a signal over bus 56 (which could be a conventional serial or parallel data bus) to each of the digital receivers 54 in turn. This signal in effect "asked" each of the digital receivers 54, one at a time, whether they had received a message. If one of digital receivers 54 responded that it had received a message, then digital selector 52 would grant that digital receiver permission to transmit its received message to it over the bus 56. Contentions for bus 56 were avoided because the only time a digital receiver 54 could transmit on the bus was when it was granted permission to do so by digital selector 52--and the digital selector would only grant such permission to one digital receiver 54 at a time.
A significant problem with the polling approach is that it introduces too much delay for PST. Each digital receiver 54 must be polled individually, and each poll takes a certain amount of time T. If N is large (i.e., there are a large number of satellite sites), the process of polling all digital receivers will take (T*N) seconds. In the worst case where a satellite site n is the only site to receive a particular RF message (from say a portable transceiver) and at the time this received message is communicated to corresponding digital receiver 54(n) the digital selector 52 has just finished polling digital receiver 54(n) and is about to poll digital receiver 54(n+1) (assuming a polling sequence in ascending order of 1-N) , it will take the full (T*N) seconds before digital selector 52 again polls digital receiver 54(n) to determine that a message has been received. Additional time will then be required to notify digital receiver 54(n) that it has been granted permission to transmit over bus 56, and still additional time is required to actually transfer the message from digital receiver 54(n) to digital selector 52.
An alternate technique used in the past to communicate messages from the digital receivers 54 to digital selector 52 uses acknowledgements to eliminate the requirement of a bus controller (and the additional time delay a controller introduces). In this alternate arrangement, an "ACK/NACK" technique is used to resolve "bus contentions" that occur whenever two digital receivers 54 try to simultaneously transmit messages over bus 56. Using this technique, each digital receiver 54 can autonomously transmit on bus 56 as soon as it receives a message so long as no other digital receiver is already actively transmitting. Digital selector 52 receives all messages transmitted on bus 56, places a responsive "acknowledgement" (ACK) message onto the bus whenever it correctly receives a message, and places a "negative acknowledgement" (NACK) message onto the bus whenever it incorrectly receives a message. Since upon the occurrence of a bus contention digital selector 52 does not correctly receive any of the contending messages, it sends a NACK signal which causes both of the transmitting digital receivers 54 to resend their messages. This technique thus avoids the time overhead involved in polling and would appear to provide a very efficient solution to a multi-site trunked digital voter.
However, this ACK/NACK arrangement described above cannot provide satisfactory performance in a digital voter for a trunking system such as GE's PST system--because it is possible and probable that multiple digital receivers will simultaneously attempt to transmit on bus 56. This is because all satellite sites typically receive a given transmitted RF message at about the same time (slight variations in receive time are attributable to different RF path lengths between the transmitting station and the satellite receiver stations) and communicate the received messages to the voter at about the same time (variations in communication time are attributable to differences in landline distance for example). Thus, it is highly probable that several versions of the same message will arrive almost simultaneously at different voter digital receivers 54. Each of the different voter digital receivers 54 may then use "carrier sense" or some other similar technique before attempting to transfer their received message to the selector to ensure that bus 56 is not in use --but will find that the bus is not in use (since none of the other digital receivers which have received versions of the same message have yet had the chance to begin transmitting). Consequently, some or all of the digital receivers 54 will begin transmitting on bus 56 virtually simultaneously--causing a "bus collision" which prevents digital selector 54 from correctly receiving any of the messages placed on the bus. While the ACK/NACK technique typically will eventually resolve the contention (e.g., especially when used in conjunction with a "random retry" or other technique preventing further bus collisions by the contending digital receivers 54), the contention resolution takes far too much time and introduces too much delay into the voting process.
Various bus contention resolution schemes are known in the computer field for efficiently resolving contentions on a common bus. The following is a (by no means exhaustive) listing of a few examples of such contention resolution schemes:
U.S. Pat. No. 4,628,311 to Milling
U.S. Pat. No. 4,623,886 to Livingston
U.S. Pat. No. 4,395,710 to Einolf Jr. et al
U.S. Pat. No. 4,638,311 to Gerety
U.S. Pat. No. 4,644,348 to Gerety
U.S. Pat. No. 4,652,873 to Dolsen et al
U.S. Pat. No. 3,701,109 to Peters
U.S. Pat. No. 4,232,294 to Burke et al
U.S. Pat. No. 4,593,282 to Acampora et al
U.S. Pat. No. 4,642,630 to Beckner et al
U.S. Pat. No. 4,583,089 to Cope
U.S. Pat. No. 4,677,612 to Olson et al
U.S. Pat. No. 4,682,324 to Ulug
U.S. Pat. No. 4,707,693 to Hessel.
However, it is not readily apparent if or how any of the techniques described in the patents listed above might be applied to a digitally trunked communication system satellite receiving site digital voter. In particular, the digital voter requirements for the GE 16 PLUS digitally trunked PST communications system are highly unusual and are not readily analogous to, for example, the peripheral bus of a computer system or a local area network (LAN).
In the case of a computer system peripheral bus or LAN, for example, the statistical probability of two nodes transmitting during a certain time period generally is directly proportional to the duration of the time period. It is relatively unlikely that two nodes will need to independently initiate a new bus communication at exactly the same instant in time (i.e., unless the bus or LAN has been unavailable for awhile because of other communications or the like or unless the peripheral communications are actually being initiated in response to the same previous bus communication). On the other hand, it may be relatively likely that two nodes will need to transmit at nearly the same time (e.g., depending upon the number of nodes on the bus/LAN and various other factors). Thus, the probability of a contention on the "macro" level (e.g., overlapping but not exactly simultaneous communications) is much higher than the probability of a contention on the "micro" level (e.g., where two nodes need to transmit beginning at almost exactly the same time). In addition, the problem of redundant contending messages (and "redundancy removal") does not exist on a LAN or peripheral bus--since all of the contending messages need to be communicated sooner or later.
In contrast, in the GE PST system presents entirely different contention problems because of system considerations. In particular, in the GE PST system all "inbound" messages are transmitted beginning at the edge of a 30 ms "slot edge" (defined by synchronization signals on the outbound control and working channels, with the sync signals on each working channel being synchronized with the control channel sync signals). If two mobile/portable transceivers attempt to transmit at or near the same time, their transmissions will either fall within different inbound slots (and thus be separated by 30 ms)--or they will fall within the same slot (and thus be virtually simultaneous). However, a contention between RF signals on the inbound control channel typically results in destroying both transmissions and causing both contending transmitters to "retry" (e.g., using random retry wait periods).
Hence, it is highly probable in the GE PST System that all satellite sites receiving a message within a given inbound "slot" will be receiving the same message. Likewise, the digital receivers 54 associated with the satellite sites will receive the corresponding digital messages (and thus need to apply the messages to the bus 56) virtually simultaneously. These messages are therefore likely to be redundant versions of the same message of which only one version needs to be selected and communicated to digital selector 52 (and the non-selected versions of which should be discarded immediately to allow the receivers to handle messages in the next incoming slot).
Hence, in the GE PST system, the probability of "macro" contentions on bus 56 is small or nonexistent, the probability of "micro" contentions is relatively high (in fact, virtually all contentions will be of the "micro" variety), and it is extremely likely that contending messages will be redundant versions of the same message.
It would be highly desirable to provide a digital voter for a high date rate digitally trunked radio communication system that eliminates data collisions on the voter bus, removes most or all redundant messages, and does not significantly impact system latency.
The present invention provides a digital voter arrangement which uses a "windowing" technique to arbitrate bus contention on an asynchronous common communication link. This digital voter arrangement reduces communication latency by entirely eliminating bus assignment by a controller (and eliminates the corresponding message overhead required by the controller), yet still prevents message collisions on the common bus. The digital voter provided by the invention also efficiently eliminates most of the redundant messages.
Briefly, a "serve request" type commmunications line (FSL) connects a plurality of digital receivers (receiving messages from corresponding plural RF receiving sites) contending for use of a serial data line (BSL) in the preferred embodiment. Data is transmitted from the digital receivers to a digital selector over the BSL. Bus collisions are prevented and redundancy removal is provided through two interrelated mechanisms.
The first mechanism relates to the FSL, which is normally in an inactive state but can be seized (controlled) by any of the plural digital receivers. When a digital receiver has received a message from its associated satellite receiver and wishes to transfer this message to the digital selector, it must first gain access to the FSL (no digital receiver is authorized to transmit on the BSL unless it has first seized the FSL). To gain access to the BSL, it tests the state of the FSL. If the FSL is inactive, the digital receiver seizes the FSL in preparation for transmitting on the BSL. In the preferred embodiment, whenever a digital receiver seizes the FSL, it continues to hold the FSL in the active state for the duration of a redundancy removal period. Any digital receiver having a message to transfer on the BSL which finds the FSL already seized assumes in the preferred embodiment that its message is redundant with the one to be transmitted by the digital receiver already controlling the FSL and therefore discards its message.
The arbitration performed by the FSL mechanism is, however, insufficient in the preferred embodiment PST trunking system to eliminate all collisions on the BSL. This is because it is possible in the GE PST trunking system that, due to the synchronized "slotted" nature of all incoming RF messages from mobile/portable transceivers, several digital receivers will successfully seize the FSL at about the same time. Thus, in this environment successful seizure of the FSL does not guarantee exclusive access to the BSL. Accordingly, a further mechanism is used to prevent BSL collisions and remove further redundant messages.
Briefly, this further mechanism in the preferred embodiment involves assigning a unique "start transmission" time window to each digital receiver contending for the BSL. Each digital receiver which has successfully seized the FSL times a duration unique to it beginning from the time it seized the FSL. During this duration, the digital receiver "listens" on the BSL for the start of transmission of a digital receiver having an "earlier" window assignment. If no start of transmission is detected by the time the digital receiver's unique delay time has elapsed, the digital receiver begins to transmit its message on the BSL. Digital receivers with "later" window assignments will detect this transmission, abort their own attempts to transmit on the BSL, and discard those messages--thus preventing message collisions on the BSL.